package primary.primary0;

public class S0416分割等和子集 {
    class Solution1 {
        /**
         * 81，和494目标和一样，01背包问题，一直不太会
         * 即元素和为num/2，正整数这个概念还是比较重要
         * 这一题，两个子集相等，就表示有一个子集的和为总和的1/2，
         * 倒着看，f(i,k)表示从0到第i位置，和为k的种类数
         * 那么 f(i,k) = f(i - 1, k) + f(i - 1, k -nums[i])
         * 因为当前这一组只和前一组有关，所以可以直接用一维的去做
         */
        public boolean canPartition(int[] nums) {
            if(nums == null || nums.length <= 1){
                return false;
            }
            int totalSum = 0;
            for(int i:nums){
                totalSum += i;
            }
            if(totalSum % 2 == 1){
                return false;
            }
            int halfSum = totalSum / 2;
            int[] record = new int[halfSum + 1];
            // 第一组，也就是第一个值取还是不取
            if(nums[0] == 0){
                record[0] = 2;
            }else{
                record[0] = 1;
                if(nums[0] <= halfSum){
                    // mark:这里初始化要讲究一下，只关心半数以下的
                    record[nums[0]] = 1;
                }
            }
            for(int i = 1; i < nums.length; i++){
                for(int j = halfSum; j >= 0; j--){
                    if(j - nums[i] >= 0){
                        record[j] = record[j - nums[i]] + record[j];
                    }else{
                        record[j] = record[j];
                    }
                }
            }
            return record[halfSum] != 0;
        }
    }

    /**
     * 看下答案
     */
    class Solution2 {
        public boolean canPartition(int[] nums) {
            int n = nums.length;
            if (n < 2) {
                return false;
            }
            int sum = 0, maxNum = 0;
            for (int num : nums) {
                sum += num;
                maxNum = Math.max(maxNum, num);
            }
            if (sum % 2 != 0) {
                return false;
            }
            int target = sum / 2;
            // 如果 maxNum>target\textit{maxNum}>\textit{target}maxNum>target，则除了 maxNum\textit{maxNum}maxNum
            // 以外的所有元素之和一定小于 target\textit{target}target，因此不可能将数组分割成元素和相等的两个子集，直接返回 false\text{false}false。
            // 这个也有意思
            if (maxNum > target) {
                return false;
            }
            // 用的是二维数组
            boolean[][] dp = new boolean[n][target + 1];
            for (int i = 0; i < n; i++) {
                // 这里只用true和false，确实不用在意有多少种
                dp[i][0] = true;
            }
            dp[0][nums[0]] = true;
            for (int i = 1; i < n; i++) {
                int num = nums[i];
                for (int j = 1; j <= target; j++) {
                    if (j >= num) {
                        dp[i][j] = dp[i - 1][j] | dp[i - 1][j - num];
                    } else {
                        dp[i][j] = dp[i - 1][j];
                    }
                }
            }
            return dp[n - 1][target];
        }
    }
}
